package com.demo.datastructure.reorder.quickSort;

import com.demo.datastructure.reorder.Example;

/**
 * @description: 三样切分快排
 * @author: ljr
 * @create: 2022/1/19 5:19 PM
 */
public class SimpleQuickSort5 implements Example {

    /**
     * 三样切分快排
     * 在数据重复元素较多的情况下，速度更快
     */
    @Override
    public void sort(Comparable[] a, int low, int high) {
        if(low >= high) return;
        int lt = low, gt = high, i = low + 1;
        Comparable v = a[low];
        while (i <= gt){
            int num = a[i].compareTo(v);
            if(num == -1){
                exch(a, i, lt);
                i++;
                lt++;
            }else if(num == 1){
                exch(a, i, gt);
                gt--;
            }
            else i++;
        }

        sort(a, low, lt-1);
        sort(a, gt+1, high);
    }
}
